Search for: All records

We investigate two discrete models of excitable media on a one-dimensional integer lattice ℤ: the κ-color Cyclic Cellular Automaton (CCA) and the κ-color Firefly Cellular Automaton (FCA). In both models, sites are assigned uniformly random colors from ℤ/κℤ. Neighboring sites with colors within a specified interaction range r tend to synchronize their colors upon a particular local event of 'excitation'. We establish that there are three phases of CCA/FCA on ℤ as we vary the interaction range r. First, if r is too small (undercoupled), there are too many non-interacting pairs of colors, and the whole graph ℤ will be partitioned into non-interacting intervals of sites with no excitation within each interval. If r is within a sweet spot (critical), then we show the system clusters into ever-growing monochromatic intervals. For the critical interaction range r=⌊κ/2⌋, we show the density of edges of differing colors at time t is Θ(t−1/2) and each site excites Θ(t1/2) times up to time t. Lastly, if r is too large (overcoupled), then neighboring sites can excite each other and such 'defects' will generate waves of excitation at a constant rate so that each site will get excited at least at a linear rate. For the special case of FCA with r=⌊2/κ⌋+1, we show that every site will become (κ+1)-periodic eventually. 

A graph homomorphism is a map between two graphs that preserves adjacency relations. We consider the problem of sampling a random graph homomorphism from a graph into a large network. We propose two complementary MCMC algorithms for sampling random graph homomorphisms and establish bounds on their mixing times and the concentration of their time averages. Based on our sampling algorithms, we propose a novel framework for network data analysis that circumvents some of the drawbacks in methods based on independent and neighborhood sampling. Various time averages of the MCMC trajectory give us various computable observables, including well-known ones such as homomorphism density and average clustering coefficient and their generalizations. Furthermore, we show that these network observables are stable with respect to a suitably renormalized cut dis- tance between networks. We provide various examples and simulations demonstrating our framework through synthetic networks. We also demonstrate the performance of our frame- work on the tasks of network clustering and subgraph classification on the Facebook100 dataset and on Word Adjacency Networks of a set of classic novels. 

In the parking model on ℤd, each vertex is initially occupied by a car (with probability p) or by a vacant parking spot (with probability 1−p). Cars perform independent random walks and when they enter a vacant spot, they park there, thereby rendering the spot occupied. Cars visiting occupied spots simply keep driving (continuing their random walk). It is known that p=1/2 is a critical value in the sense that the origin is a.s. visited by finitely many distinct cars when p<1/2, and by infinitely many distinct cars when p≥1/2. Furthermore, any given car a.s. eventually parks for p≤1/2 and with positive probability does not park for p>1/2. We study the subcritical phase and prove that the tail of the parking time τ of the car initially at the origin obeys the bounds exp(−C1tdd+2)≤ℙp(τ>t)≤exp(−c2tdd+2) for p>0 sufficiently small. For d=1, we prove these inequalities for all p∈[0,1/2). This result presents an asymmetry with the supercritical phase (p>1/2), where methods of Bramson--Lebowitz imply that for d=1 the corresponding tail of the parking time of the parking spot of the origin decays like e−ct√. Our exponent d/(d+2) also differs from those previously obtained in the case of moving obstacles. 

Political elites both respond to public opinion and influence it. Elite policy messages can shape individual policy attitudes, but the extent to which they do is difficult to measure in a dynamic information environment. Furthermore, policy messages are not absorbed in isolation, but spread through the social networks in which individuals are embedded, and their effects must be evaluated in light of how they spread across social environments. Using a sample of 358 participants across thirty student organizations at a large Midwestern research university, we experimentally investigate how real social groups consume and share elite information when evaluating a relatively unfamiliar policy area. We find a significant, direct effect of elite policy messages on individuals’ policy attitudes. However, we find no evidence that policy attitudes are impacted indirectly by elite messages filtered through individuals’ social networks. Results illustrate the power of elite influence over public opinion.